import React, {Component} from 'react';
import Markdown from 'react-markdown';
import {Anchor, Row, Col} from 'antd';


class JsPage extends Component {
    constructor(props) {
        super(props);
    }


    render() {

        return (
            <div>
                <Markdown source={"# Hashmap的死循环\n\n" +
                "简单地说一下HashMap这个经典的数据结构\n\n" +
                "HashMap通常会用一个指针数组（假设为table[]）来做分散所有的key，当一个key被加入时，会通过Hash算法通过key算出这个数组的下标i，然后就把这个&lt;key, value>插到table\\[i]中，如果有两个不同的key被算在了同一个i，那么就叫冲突，又叫碰撞，这样会在table\\[i]上形成一个链表。\n\n" +
                "如果table[]的尺寸很小，比如只有2个，如果要放进10个keys的话，那么碰撞非常频繁，于是一个O(1)的查找算法，就变成了链表遍历，性能变成了O(n)\n\n" +
                "Hash表的尺寸和容量非常的重要。一般来说，Hash表这个容器当有数据要插入时，都会检查容量有没有超过设定的thredhold，如果超过，需要增大Hash表的尺寸，但是这样一来，整个Hash表里的无素都需要被重算一遍。这叫rehash，这个成本相当的大。\n\n" +
                "检查容量是否超标\n\n" +
                "```\n\n" +
                "void addEntry(int hash, K key, V value, int bucketIndex)\n" +
                "{\n" +
                "    Entry&lt;K,V> e = table[bucketIndex];\n" +
                "    table[bucketIndex] = new Entry&lt;K,V>(hash, key, value, e);\n" +
                "    //查看当前的size是否超过了我们设定的阈值threshold，如果超过，需要resize\n" +
                "    if (size++ >= threshold)\n" +
                "        resize(2 * table.length);\n" +
                "}\n" +
                "```\n\n" +
                "新建一个更大尺寸的hash表，然后把数据从老的Hash表中迁移到新的Hash表中。\n\n" +
                "```\n\n" +
                "void resize(int newCapacity)\n" +
                "{\n" +
                "    Entry[] oldTable = table;\n" +
                "    int oldCapacity = oldTable.length;\n" +
                "    ......\n" +
                "    //创建一个新的Hash Table\n" +
                "    Entry[] newTable = new Entry[newCapacity];\n" +
                "    //将Old Hash Table上的数据迁移到New Hash Table上\n" +
                "    transfer(newTable);\n" +
                "    table = newTable;\n" +
                "    threshold = (int)(newCapacity * loadFactor);\n" +
                "}\n" +
                "```\n\n" +
                "数据迁移到New Hash Table上\n\n" +
                "```\n\n" +
                "void transfer(Entry[] newTable)\n" +
                "{\n" +
                "    Entry[] src = table;\n" +
                "    int newCapacity = newTable.length;\n" +
                "    //下面这段代码的意思是：\n" +
                "    //  从OldTable里摘一个元素出来，然后放到NewTable中\n" +
                "    for (int j = 0; j < src.length; j++) {\n" +
                "        Entry<K,V> e = src[j];\n" +
                "        if (e != null) {\n" +
                "            src[j] = null;\n" +
                "            do {\n" +
                "                Entry<K,V> next = e.next;\n" +
                "                int i = indexFor(e.hash, newCapacity);\n" +
                "                e.next = newTable[i];\n" +
                "                newTable[i] = e;\n" +
                "                e = next;\n" +
                "            } while (e != null);\n" +
                "        }\n" +
                "    }\n" +
                "}\n```\n\n" +
                "新的hash表会反转oldhash表，先进后出；" +
                "### 并发下的Rehash\n\n" +
                "我们再回头看一下我们的 transfer代码中的这个细节：\n\n" +
                "```\n" +
                "do {\n" +
                "    Entry<K,V> next = e.next; // <--假设线程一执行到这里就被调度挂起了\n" +
                "    int i = indexFor(e.hash, newCapacity);\n" +
                "    e.next = newTable[i];\n" +
                "    newTable[i] = e;\n" +
                "    e = next;\n" +
                "} while (e != null);\n```\n\n" +
                "而我们的线程二已经把上面的代码执行完成了,线程二过后的hash表已经反转了！线程I拿着线程II反转后链表进行rehash，就回出现e.next形成链一个环；当get相同槽上而不存在的key时，就会进入无限循环中，Infinite Loop 无穷循环。有人把这个问题报给了Sun，不过Sun不认为这个是一个问题。因为HashMap本来就不支持并发。要并发就用ConcurrentHashmap。\n\n" +
                "发生无限循环后会有什么问题呢？\n\n" +
                "线程会一直执行，处于RUNABLE状态，top线程会发现TIME+运行时间很长; 现象: **较少发生OOM,load增高。** \n\n"}/>
            </div>

        );
    }
}

export default JsPage;